//快速排序【分治递归】
/*
    在待排序表L【1……n】中任取一个元素pivot作为枢纽(或基准，通常取首元素)，通过一趟排序将待排序表划分为独立的两部分L【1……k-1】
和L【k+1……n】，使得L【1……k-1】中的所有元素都小于pivot，L【k+1……n】中的所有元素大于等于pivot，则pivot放在了其最终位置L[k]上，
这个过程称为一次"划分"。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。
*/
/*
    不稳定
    平均时间复杂度O(nlogn)【每次划分很平均】，最坏时间复杂度O(n^2)【原本就有序会退化为冒泡排序】;
    最好空间复杂度O(logn)，最坏空间复杂度O(n);
*/

#include <iostream>

using namespace std;

//把第一个元素当作枢轴(基准)pivot将待排序序列划分为左右两个部分，并返回枢轴pivot最终位置的索引
int Partition(int A[], int low, int high) //注意:这里的low、high是数组A中要排序区间的左端点和右端点的索引
{
    int pivot = A[low]; //把第一个元素作为枢轴pivot
    while (low < high)  //用low、high索引搜索枢轴的最终位置
    {
        //找到右边比枢轴元素小的元素移动到左端
        while (low < high && A[high] >= pivot)
            --high;
        A[low] = A[high];

        //找到左边比枢轴元素大的元素移动到右端
        while (low < high && A[low] <= pivot)
            ++low;
        A[high] = A[low];
    }
    A[low] = pivot; //枢轴元素pivot存放到最终位置(此时low==high)
    return low;     //返回存放枢轴pivot的位置
}

//快速排序
void QuickSort(int A[], int low, int high) //递归实现，可对比二叉树的先序遍历(根左右)【先分再继续处理(分)左右两子部分】
{
    if (low < high) //递归跳出条件
    {
        int pivotPos = Partition(A, low, high); //【根】"划分"操作，并把pivot的位置保存下来，以便下一层递归划分
        QuickSort(A, low, pivotPos - 1);        //【左】对左子表递归快速排序
        QuickSort(A, pivotPos + 1, high);       //【右】对右子表递归快速排序
    }
    return;
}

//测试代码
int main()
{
    int A[100] = {2, 4, 3, 7, 9, 1, 6, 5, 8};
    QuickSort(A, 0, 8);
    for (int i = 0; i < 9; ++i)
        cout << A[i] << ' ';
    return 0;
}